package practise.alogrithm.hundredInterviewQuestions.secondTime;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

/**
 * Created by Richard on 7/25/2014.
 */
public class ConvertTreeToBidirectionLinkList {
    public static TreeNode convert(TreeNode node,TreeNode previous){
        if(node.getLeft()==null && node.getRight()==null){
            if(previous!=null){
                previous.setRight(node);
                node.setLeft(previous);
            }
            return node;
        }
        if(node.getLeft()!=null){
            previous = convert(node.getLeft(),previous);

            previous.setRight(node);
            node.setLeft(previous);
            previous = node;
        }
        if(node.getRight()!=null)
            previous = convert(node.getRight(),previous);
        return previous;
    }

    public static void main(String[] args){
        TreeNode treeNode = TreeBuilder.createTreeByArrayInWidth(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16});
        treeNode = convert(treeNode,null);
        while (treeNode!=null){
            System.out.print("<=="+treeNode.getValue());
            treeNode = treeNode.getLeft();
        }
    }
}
